/*
 * @作者: 沙昊
 * @邮箱: shahao@zju.edu.cn
 * @功能: 
 * @包含算法: 
 * Copyright (c) 2023 by 沙昊, All Rights Reserved. 
 */
/*
/**

 */

 struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 };

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param p int整型 
     * @param q int整型 
     * @return int整型
     */
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        // write code here
        TreeNode* ancestor = root;
        while(true){
            if(p < ancestor->val && q< ancestor->val){
                ancestor =  ancestor->left;
            }
            else if(p > ancestor->val && q > ancestor->val){
                ancestor = ancestor->right;
            }
            else{
                break;
            }
        }
        return ancestor->val;
    }
};


/*
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）
*/

int test(vector<int>& height){
    if(height.size()<=2) return 0;
    int size = height.size();
    vector<int> left(size,0);
    vector<int> right(size,0);

    left[0] = height[0];
    for(int i=1; i<size; i++){
        left[i] = max(height[i],left[i-1]);
    }
    right[size-1] = height[size-1];
    for(int j= size-2; j>=0; j--){
        right[i] = max(height[i], right[i+1]);
    }

    int result=0;
    for(int k=0; k<size; k++){
        int count = min(left[i],right[i])-height[i];
        if(count<0) continue;
        result += count; 
    }
    return result;
}